package SlidingWindow;

import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName LC438
 * @Description TODO
 * @Author ZJX
 * @Date 2024/9/20 14:10
 * @Version 1.0
 */
public class LC438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        if (s == null || p == null || s.length() < p.length()){
            return result;
        }

        // 用数组模拟 map 记录 p 中每个字符的频率
        int[] count = new int[26];
        // 统计 p 的字符频率
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }

        int needMatch = p.length(); // 需要匹配的字符数
        int left = 0;               // 滑动窗口左边界

        for (int right = 0; right < s.length(); right++) {
            // 如果当前字符在 count 中的频率大于 0，说明 p 中包含这个字符
            if (count[s.charAt(right) - 'a'] > 0) {
                needMatch--;
            }
            // 减少窗口中当前字符的计数
            count[s.charAt(right) - 'a']--;

            if ((right - left + 1) == p.length()){
                if (needMatch == 0){
                    result.add(left);
                }
                // 移动左指针，恢复窗口左边字符的频率
                if (count[s.charAt(left) - 'a'] >= 0) {
                    needMatch++;
                }
                count[s.charAt(left) - 'a']++;
                left++; // 左指针向右移动
            }
        }
        return result;
    }
}
